package com.example.leetcode.trainingcamp.week8.sunday;

import java.util.ArrayList;
import java.util.List;

public class Test131 {

    private List<List<String>> result = new ArrayList<>();


    public List<List<String>> partition(String s) {
        char[] chars = s.toCharArray();
        backtrack(chars,0,new ArrayList<>());
        return result;
    }

    public void backtrack(char[]chars ,int begin,List<String> list ){
        if (chars.length == begin){
            result.add(new ArrayList<>(list));
            return;
        }
        for (int i = begin;i<chars.length;i++){
            if (is(begin,i,chars)){
                list.add(new String(chars, begin, i + 1 - begin));
                backtrack(chars,i+1,list);
                list.remove(list.size()-1);
            }
        }
    }

    public boolean is(int left ,int right,char[] chars){
        while (left < right){
            if (chars[left] != chars[right]) return false;
            left++;
            right--;
        }
        return true;
    }
}

class Demo131{
    public static void main(String[] args) {
        Test131 t = new Test131();
        String s = "aab";
        List<List<String>> partition = t.partition(s);
        for (List<String> list:partition) {
            for (String s1:list) {
                System.out.print(s1+" ");
            }
            System.out.println();
        }
    }
}